
/*
Description:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class MinStack {
public:
	/** initialize your data structure here. */
	MinStack() {
		_data.reserve(0);
	}

	void push(int x) {
		_data.push_back(x);
	}

	void pop() {
		_data.pop_back();
	}

	int top() {
		return _data.back();
	}

	int getMin() {		//retrieving the minimum element in constant time.!!!
		auto pos = std::min_element(_data.begin(), _data.end());
		return *pos;
	}

	vector<int> _data;
};

class MinStack1 {
	vector<int> a;
	int min;
public:
	/** initialize your data structure here. */
	MinStack1() {
		min = INT_MAX;
	}

	void push(int x) {
		if (x <= min) {
			a.push_back(min);
			min = x;
		}
		a.push_back(x);
	}

	void pop() {
		int t = a.back(); a.pop_back();
		if (t == min) {
			min = a.back();
			a.pop_back();
		}
	}

	int top() {
		return a.back();
	}

	int getMin() {
		return min;
	}
};

class MinStack2 {
private:
	stack<int> s1;
	stack<int> s2;
public:
	void push(int x) {
		s1.push(x);
		if (s2.empty() || x <= getMin())  s2.push(x);
	}
	void pop() {
		if (s1.top() == getMin())  s2.pop();
		s1.pop();
	}
	int top() {
		return s1.top();
	}
	int getMin() {
		return s2.top();
	}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/

int _MinStack()
{
	MinStack minStack = MinStack();
	
	minStack.push(-2);
	minStack.push(0);
	minStack.push(-3);
	int param_2 = minStack.getMin();   //--> Returns - 3.
	minStack.pop();
	int param_3 = minStack.top();      //--> Returns 0.
	int param_4 = minStack.getMin();   //--> Returns - 2.

	cout << param_2 << " " << param_3 << " " << param_4 << endl;

	return 0;
}